The present invention relates to a method for encrypting information into a code which cannot be deciphered by an eavesdropper and a method of decrypting the code to recover the original information.
Typical of encrypting and decoding methods heretofore proposed is a RSA method which is disclosed by R. L. Rivest, A. Shamir and L. Addleman in a paper entitled "A Method for Obtaining Digital Signatures and Public-key Cryptosystems", Comm. ACM, Vol. 21, No. 2, pp. 120-126, 1978. For convenience of description, the following description will concentrate only on a case wherein information is encrypted into a cryptogram for the purpose of preventing an unauthorized person from eavesdropping on the information. The encrypting and decrypting methods will be limited to the RSA method by way of example. Let the manipulation for converting information into a cryptogram and the manipulation for decrypting a cryptogram into original information be called encrypting and decrypting respectively. The encrypting and decrypting procedures according to the RSA method use an encrypting key e and a decrypting key d each being represented by a numerical value, and a common key n shared by both encrypting and decrypting also being represented by a numerical value. These numerical values e, d, and n are predetermined integers. How to select the numerical values e, d, and n is not directly relevant to the present invention and therefore will not be described herein. The encrypting procedure particular to the RSA method begins with the step of obtaining a numerical representation P of the information. Since information is usually rendered in the form of a bit sequence of logical ZEROs and logical ONEs, it will be automatically represented by a numerical value if the bit sequence is divided into blocks each having a finite length. In the following description, therefore, information and a numerical representation of information will not be distinguished from each other so long as there is no chance of confusion. A cryptogram C is obtained by applying to the information an arithmetic operation: EQU C=P.sup.e mod n
Specifically, the information is raised to power e and then divided by n, the residual being the cryptogram C. To recover the original information P from the cryptogram C, the following arithmetic operation is performed: EQU P=C.sup.d mod n
This equation means that the cryptogram C is raised to power d and then divided by n, the residue being the information P.
The RSA method, as discussed in the previously mentioned paper, is designed to be elaborate not only to prevent an unauthorized person from eavesdropping on the information but also to eliminate occurrences in which a person who transmitted the information later denies the transmission because of fraud and in which an unauthorized person transmits information pretending to be an authorized person.
A problem with the prior art encrypting and decrypting methods discussed above is that the information P has to be smaller than the common key n. Otherwise the information rendered by a numerical representation P and the information rendered by a numerical representation P+n would become indistinguishable because a residual produced by the division by the common key n is computed during the course of encrypting operation. Further, to conform to the binary notation adopted for communications and computers, input information is usually divided so that the information P to be encrypted is one bit shorter than the common key n. Moreover, since information applicable to communications and computers is managed by being fractioned to a length of 2's power such as 1024 bits, even the increase in the bit length by one amounts to an increase by 1024 in total. Thus, the prior art encrypting method critically degrades the transmission of information and the efficiency of storage.